package top.ivansong92.example.leetcode.learning.sort;


import org.junit.Test;

public class TestExample {
    /**
     * 合并两个有序数组
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/8/sorting-and-searching/52/
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0, k = 0;
        int[] res = new int[nums1.length];
        while(j < n || i < m) {
            if (j >= n) {
                res[k++] = nums1[i++];
                continue;
            }
            if (i >= m) {
                res[k++] = nums2[j++];
                continue;
            }
            if (nums1[i] < nums2[j]) {
                res[k++] = nums1[i++];
            } else {
                res[k++] = nums2[j++];
            }
        }

        k = 0;
        for(;k < res.length; k ++) {
            nums1[k] = res[k];
        }
    }
    @Test
    public void test1() {
        merge(new int[]{1, 0}, 1, new int[]{2}, 1);
    }


    /**
     * 第一个错误的版本
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/8/sorting-and-searching/53/
     * @param n
     * @return
     */
    public int firstBadVersion(int n) {
        if (n == 1) {
            if (isBadVersion(n)) {
                return 1;
            }
            return 0;
        }
        if (n == 2) {
            if (isBadVersion(1)) {
                return 1;
            }
            if (isBadVersion(2)) {
                return 2;
            }
            return 0;
        }
        if (n == 3) {
            if (isBadVersion(1)) {
                return 1;
            }
            if (isBadVersion(2)) {
                return 2;
            }
            if (isBadVersion(3)) {
                return 2;
            }
            return 0;
        }
        int k = n / 2;
        while (k > 1 && k < n) {
            boolean res0 = isBadVersion(k - 1);
            if (res0) {
                k = (k + 1) / 2;
                continue;
            }
            boolean res1 = isBadVersion(k);
            if (res1) {
                return k;
            }
            boolean res2 = isBadVersion(k + 1);
            if (res2) {
                return k + 1;
            }

            k = k + (n - k) / 2;
        }
        return k;
    }

    public int firstBadVersion2(int n) {
       int left = 1;
       int right = n;
       while (left < right) {
           int mid = left + (right - left) / 2;
           if (isBadVersion(mid)) {
               right = mid;
           } else {
               left = mid + 1;
           }
       }
       return left;
    }


    private boolean isBadVersion(int version) {
        return true;
    }
}